1.1-1.2 马氏链、不变分布、可逆分布

第一章 马氏链

1.1 定义与例子

• 定义1. $p_{ij} \geq 0$，$\sum_{j \in S} p_{ij} = 1$. 得到矩阵$P$。称之为$S$上的一个转移概率矩阵，或转移矩阵。称$p_{ij}$为从$i$到$j$的转移概率。

• 定义2. 若转移矩阵$P$使得

  $$P(X_{n+1}= j | X_{n} = i, X_0 = i_0, \cdots, X_{n-1} = i_{n-1}) = p_{ij}$$

  则称$\{X_n\}$ 是$S$上的一个**（时齐的）马尔科夫链**。

例子：

1. （d维）简单随机游动
2. 两状态马氏链
3. 图上的随机游动

有限维联合分布

• 命题1. 令$Y_n = X_{n+m}$. 那么，在$X_n=i$的条件下，$\{Y_m\}$是从$i$出发的马氏链，且它与$(X_0,\cdots,X_{n-1})$独立。

记$P(X_{m+n}=j|X_n=i)$为$p_{ij}^{(m)}$.

• 命题2. （$Chapman-Kolmogrov$ 等式）

  $$p_{ij}^{(n+m)} = \sum _{k \in S} p_{ik}^{(n)}p_{kj}^{(m)}$$

• 推论：$p_{ij}^{(n)}=(P^n)_{ij}$

称$P^n$为$n$步转移矩阵。

马氏链的构造（递归）

设$P$是一个转移矩阵，$\mu$为$S$上的一个分布。取独立同分布的随机变量序列$U_0,U_1,\cdots,$使得$U_i$服从$(0,1)$上的均匀分布。

取$g: (0,1] \rightarrow S$ 使得

$$g(u) :=i, \ \forall u \in \Big(\sum_{r=1}^{i-1} \mu_j, \sum_{r=1}^i \mu_j \Big]$$

那么，

$$P(g(U_0)=i) = P\Big(\sum_{r=1}^{i-1} \mu_j < U \leq \sum_{r=1}^i \mu_j \Big) = \mu_j$$

即 $g(U_0) \sim \mu$

$g$刻画了初始分布

取$f(i,·): (0,1] \rightarrow S$ 使得

$$f(i,u) :=j, \ \forall u \in \Big(\sum_{r=1}^{j-1} p_{ir}, \sum_{r=1}^j p_{ir} \Big]$$

那么，

$$P(f(i,U_n)=i) = P\Big(\sum_{r=1}^{j-1} p_{ir} < U \leq \sum_{r=1}^j p_{ir} \Big) = p_{ij}$$

$f$刻画了转移矩阵

令$X_0 := g(U_0)$，并递归定义$X_{n+1}:= f(X_n, U_{n+1})$.

1.2 不变分布与可逆分布

• 定义1. 假设$\pi = \{\pi_j:j \in S \}$为$S$上的测度。若$\pi$满足以下不变方程：

$$\pi_j = \sum_{k \in S} \pi_k \ p_{kj}, \quad \forall j \in S$$

​ 则称$\pi$为$P$的一个不变测度。若$\pi$还是分布，则称为不变分布。

假设 $\pi$ 为不变分布。如果 $X_0 \sim \pi$，那么，

$$(X_0, X_1, \cdots, X_n) \stackrel{d}{=} (X_m, X_{m+1}, \cdots, X_{m+n}), \quad n, m \geqslant 1,$$

其中，“$\stackrel{d}{=}$”表示同分布。满足上式的过程被称为平稳过程。对于一个平稳过程，任意时刻 $m$ 都可以被视为时间起点。对于马氏链而言，因为同样的初分布带来同样的有限步轨道分布。因此，不变分布也被称为平稳分布。

• 寻找不变分布的方法：

1. 若$S$有限，则可将$\pi$视为行向量，我们有$\pi = \pi P$，即$\pi$是$P$的特征值为$1$的行向量。

2. 对$S$的任意子集$A$，

   $$\sum_{i \neq 1, j \in A} \pi_i p_{ij} = \sum_{i \in A, j \notin A} \pi_i p_{ij}$$

   此式与$\pi$是不变分布等价。

3. 利用空间的平移不变性。

细致平衡条件:

$$\quad \pi_i p_{ij} = \pi_j p_{ji}, \quad \forall \, i, j \in S$$

• 定义2. 假设 $P$ 不可约，$\pi$ 为 $S$ 上的一个测度。若细致平衡条件成立，则称 $\pi$ 为 $P$ 的配称测度。此时，称 $P$ 为可配称的。进一步，若 $\pi$ 是一个分布，则称 $\pi$ 为 $P$ 的可逆分布。此时，称 $P$ 为可逆的。

一个转移矩阵不可约指的是从任意一个状态都可以到达任意一个状态。

• 定义3. 设$\pi$是不变分布。固定$N$，令$Y_n := X_{N-n}$，则$\{Y_n: 0 \leq n \leq N\}$被称为$\{X_n: 0 \leq n \leq N\}$的时间倒逆过程，简称逆过程。$\{Y_n: 0 \leq n \leq N\}$的转移概率为

$$\tilde{p}_{ij} = \frac{\pi_j p_{ji}}{\pi_i}, \quad \forall i, j \in S.$$

因此，$\pi$是可逆分布指$\tilde{P} = P$。

• 求可逆分布的方法：

  1. 取定$o$，记$S_0=\{o\}$。

  2. 归纳定义从$o$出发经过$n$步之后才能到达的状态，这样的状态构成集合$S_n$。

     假设 $\bigcup_{n=0}^{\infty} S_n = S$。对任意 $i \in S_n$，随便取一个 $k \in S_{n-1}$ 使得 $p_{ki} > 0$，并令

     $$\pi_i = \frac{\pi_k p_{ki}}{p_{ik}}.$$

  3. 验证细致平衡条件，并进一步将 $\pi$ 归一化，结论为以下三种情形之一。

     情形一、存在两个状态 $i, j$ 使得 $\pi_i p_{ij} \neq \pi_j p_{ji}$。那么$P$ 没有配称测度，从而也没有可逆分布。

     情形二、细致平衡条件 (1.2.4) 成立，但 $\pi$ 不可以归一化。那么$P$ 有配称测度，但没有可逆分布。

     情形三、细致平衡条件 (1.2.4) 成立，且 $\pi$ 可以归一化。那么可取到恰当的 $\pi_o$ 使得 $\pi$ 就是 $P$ 的可逆分布。

• 定理1**(更新定理)**. 假设$L_1, \cdots$独立同分布，取非负整数，$P(L_1=0)<1$。令$S_0=0,S_r=L_1+\cdots+L_r$。令$R_n=max\{r \geq 0:S_r \leq n\}$。则有

$$P \Big(\lim_{n \rightarrow \infty} \frac{R_n}{n} = \frac{1}{EL_1} \Big) =1$$